package com.lun.swordtowardoffer2.c14;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LenLongestFibSubseq {

	//我写的
	public int lenLongestFibSubseq(int[] A) {
		if(A == null || A.length < 3) {
			return 0;
		}
		int max = 2;
		
		int[][] dp = new int[A.length][A.length];
		
		for(int i = 1; i < A.length; i++) {
			for(int j = 0; j < i; j++) {
				if(j == 0) {
					dp[i][j] = 2;
					continue;
				}
				int target = A[i] - A[j]; 
				int index = Arrays.binarySearch(A, 0, j, target);
				if(index > -1) {
					dp[i][j] = dp[j][index] + 1;
					max = Math.max(max, dp[i][j]);
				}
			}
		}
		
		return max > 2 ? max : 0;
	}
	
	
	//书上的
	public int lenLongestFibSubseq2(int[] A) {
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < A.length; i++) {
			map.put(A[i], i);
		}
		
		int[][] dp = new int[A.length][A.length];
		int max = 2;
		for(int i = 1; i < A.length; i++) {
			for(int j = 0; j < i; j++) {
				int k = map.getOrDefault(A[i] - A[j], -1);
				dp[i][j] = k >= 0 && k < j ? dp[j][k] + 1 : 2;
				max = Math.max(max, dp[i][j]);				
			}
		}
		
		return max > 2 ? max : 0;
	}
	
}
